package two.tree;

/**
 * 验证二叉搜索树:
 * 时间复杂度：O(n)
 * 思路：递归（边界、本层逻辑、子问题、还原现场）
 *     1）节点的左子树只包含小于当前节点的数。==》左子树最大值小于当前节点
 *     2）节点的右子树只包含大于当前节点的数。==》右子树最小值大于当前节点
 *     3）所有左子树和右子树自身必须也是二叉搜索树。
 */
public class IsValidBST {
    public boolean isValidBST(TreeNode root) {
        return check(root).isValid;
    }

    private class Info{
        public boolean isValid;
        public long minVal;
        public long maxVal;
    }
    private Info check(TreeNode root){
        if(root == null){ //边界
            Info info = new Info();
            info.isValid = true;
            info.minVal = Integer.MIN_VALUE + 1L; //注意点
            info.maxVal = Integer.MAX_VALUE - 1L;
            return info;
        }
        //子问题
        Info left = check(root.left);
        Info right = check(root.right);
        //本层逻辑
        Info result = new Info();
        result.isValid = left.isValid && right.isValid && left.maxVal < root.val && right.minVal > root.val;
        result.minVal = Math.min(root.val, Math.min(left.minVal, right.minVal));
        result.maxVal = Math.max(root.val, Math.max(left.maxVal, right.maxVal));

        return result;
    }
}
